// hard

// 给定一个二叉树的根节点root，要求：返回其最大路径和
// 路径：从树中的任意节点出发，沿着父节点-子节点连接，到大任意子节点的序列，同一个节点在一条路径上最多出现一次，该路径至少包含一个节点，且不一定经过根节点
// 路径和：路径中各节点值的总和

// 解题思路：深度优先搜索遍历二叉树，递归的同时，维护一个最大路径和变量，定义函数dfs(root), 计算二叉树中以该节点为根节点，并经过该节点的最大贡献值
// 计算的结果可能的情况有2种：
// 经过该空节点的最大贡献值等于0
// 经过非空节点的最大贡献值等于当前节点 + 左右子节点的最大贡献值中较大的一个

// 在递归时，我们先计算左右子节点的最大贡献值，再更新维护当前最大路径和变量
// 最终max_sum即为答案



function maxPathSum(root) {
    let max_sum = Number.MIN_SAFE_INTEGER
    function dfs(root) {
        if (!root) {
            return 0
        }
        let left_max = Math.max(dfs(root.left), 0)
        let right_max = Math.max(dfs(root.right), 0)
        max_sum = Math.max(max_sum, root.val + left_max + right_max)
        return root.val + Math.max(left_max, right_max)
    }
    dfs(root)
    return max_sum
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
        },
        right: {
            val: 5,
        },
    },
    right: {
        val: -6,
    },
};

console.log(maxPathSum(root));